package 哈希表;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @Author Weton Li
 * @Date 2021/3/7 21:20
 */
public class 七_寻找重复数_集合保存法 {

    public static int searchDuplicate1(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            if (hashMap.containsKey(num)) {
                return num;
            } else {
                hashMap.put(num, 1);
            }
        }
        return -1;
    }

    public static int searchDuplicate2(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            if (hashSet.contains(num)) {
                return num;
            } else {
                hashSet.add(num);
            }
        }
        return -1;
    }

    public static int searchDuplicate3(int[] nums) {
        int leftp = 1;
        int rightp = nums.length - 1;



        while (leftp <= rightp) {

            int mid = (leftp + rightp) / 2; // 每轮，mid重新计算
            int count = 0; // 计数器定义每轮从0开始。

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (mid >= count) { // 小于mid的数的数量 小于等于 中间值
                leftp = mid + 1; // 二分，在右边部分
            } else {
                rightp = mid; // 在左半部分
            }
            if (leftp == rightp) { // 当左右指针相遇，找到重复数
                return leftp;
            }
        }
        return -1;
    }

    public static int searchDuplicate4(int[] nums){
        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]]; // 一次走两步
        }while (fast!=slow);

        int before = 0;
        int after = slow;
        while (before != after) {
            before = nums[before];
            after = nums[after];
        }
        return before;
    }

    public static void main(String[] args) {
        int[] input1 = {1, 3, 4, 2, 2,6}; // 2
        int[] input2 = {1, 1, 2}; // 1
        System.out.println(searchDuplicate4(input1));
    }
}
